package L618;

import util.ListNode;

/**
 * @program: javase
 * @description: 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * 示例 1:  给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 * 5->4->3
 * 1->2
 * @author: luolidong
 * @create: 2021-06-18 17:02
 * @version: 1.0
 */
public class Demo1 {
    public void reorderList(ListNode head) {
        ListNode h1 = head;
        int length = 0;
        while (h1 != null) {
            length++;
            h1 = h1.next;
        }
        // System.out.println(length);

        h1 = head;
        ListNode h3 = h1;
        ListNode h4 = null;
        int count = 1;
        while (count < length / 2) {
            h1 = h1.next;
//            System.out.println(h1);
            count++;
            if (count == length / 2) {
                h4 = h1.next;
                h1.next = null;
            }
        }
        ListNode h5 = reserve(h4);
//        System.out.println(h3);
//        System.out.println(h5);

        ListNode build = build(h3, h5);
        head=build;
//        System.out.println(build);
    }

    public ListNode reserve(ListNode head) {
        ListNode cur = head, pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //     * 5->4->3
// * 1->2
    public ListNode build(ListNode l1, ListNode l2) {
        ListNode l3 = l1, l4 = l2, cur = new ListNode(0);
        ListNode dummy = new ListNode(0);
        dummy = cur;
        int num = 1;
        while (l1 != null &&l2 != null) {
//            ListNode next1=l1.next;
//            ListNode next2=l2.next;
            if (num % 2 == 1) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
            num++;
            System.out.println(cur);
        }
        cur.next=l1==null? l2:l1;
        return dummy.next;
    }

    public static void main(String[] args) {
        new Demo1().reorderList(ListNode.build());

    }
}
